// 栈
// "消消乐" 问题，要想到使用栈的思想解决

// 例题 1：
// 给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
// 在 s 上反复执行重复项删除操作，直到无法继续删除。
// 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
//
//        示例：
//
//        输入："abbaca"
//        输出："ca"
//        解释：
//        例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
//
//
//        提示：
//
//        1 <= s.length <= 105
//        s 仅由小写英文字母组成。

// 解题思路：
// 相邻的字符消除 - 是典型的“消消乐”问题，可以使用栈的思想解决
// 字符不同，执行进栈操作，字符相同，执行出栈操作

public class RemoveDuplicates {
    public String removeDuplicates(String s) {
        int n = s.length();
        StringBuilder ret = new StringBuilder();
        char[] sArr = s.toCharArray();
        int pos = 0;
        for(int i = 0; i < n; i++){
            if(pos > 0 && ret.charAt(pos - 1) == sArr[i]){
                ret.deleteCharAt(pos - 1);
                pos--;
            } else {
                ret.append(sArr[i]);
                pos++;
            }
        }
        return ret.toString();
    }
}
